package com.linwen.excise.leetcode;

import com.linwen.dataStructure.tree.BinaryTree;
import com.linwen.dataStructure.tree.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 给出一个完全二叉树，求出该树的节点个数。
 *
 * 说明：
 *
 * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author : linwen
 * @date : 上午12:27 2020/11/25
 */
public class _222完全二叉树的节点个数 {
    public static void main(String[] args) {
        //构造二叉树
        LinkedList<Integer> inputList = new LinkedList<Integer>
                (Arrays.asList(new Integer[] {1,2,3,4,5,6}));
        new BinaryTree();
        com.linwen.dataStructure.tree.TreeNode treeNode = BinaryTree.creatBinaryTree(inputList);
        System.out.println(countNodes1(treeNode));
    }

    private static int countNodes1(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = countLevel(root.leftNode);
        int right = countLevel(root.rightNode);
        if(left==right){
            return countNodes1(root.rightNode) + (1<<left);
        }else{
            return countNodes(root.leftNode) + (1<<right);
        }
    }

    private static int countLevel(TreeNode Node) {
        int level = 0;
        while (Node!=null){
            level++;
            Node = Node.leftNode;
        }
        return level;
    }

    private static int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return countNodes(root.leftNode) + countNodes(root.rightNode) + 1;

    }
}
